1. Field of the Invention
The invention relates in general to a method for motion estimation in video encoding, and more particularly to a method using a motion vector predictor for motion estimation in video encoding.
2. Description of the Related Art
Nowadays, the multimedia field has become very popular and is widely applied in our daily life. In recent years, it has become a trend to use MPEG-4 for the multimedia image. The platform for MPEG-4 demands flexibility of applying multiple and different equipment, and powerful capability of data processing in order to achieve instant effect which is required when processing image. Since a multimedia processor combines the flexibility of a programmable processor and the computing ability of a parallel architecture, it is chosen as a platform of an image processing system.
In the process of image encoding, most of the computing resource is occupied by block matching motion estimation. The easiest and most complete method of motion estimation is the full search algorithm. When proceeding with the block matching motion estimation, the algorithm compares each block of a reference frame respectively with a block of a current frame, and thus results in the best-matching block in the reference frame for the block of the current frame.
Each block corresponds to a checking point. Referring to FIG. 1, it illustrates the relation between the checking points and the blocks. For example, the checking points A and A1 respectively correspond to the blocks 102 and 104 in a reference frame. If the checking point A is moved left and downward by one pixel, it becomes the checking point A1. In this way, when the block 102 is shifted left and downward by one pixel, it results in the block 104.
The full search algorithm, as the term suggests, takes every point of a search region as a checking point, and compares all pixels between the blocks corresponding to all checking points of the reference frame and the block of the current frame. Then the best checking point is determined to obtain a motion vector value. The comparison technique is performed by computing the difference in the image information of all corresponded pixels, and then summing the absolute values of the differences in the image information. Finally, the sum of absolute difference (SAD) is performed. Then, among all checking points, the checking point with the lowest SAD is determined to be the best checking point. The block that corresponds to the best checking point is the block of the reference frame matching best with the block of the current frame that is to be encoded. And a motion vector can be obtained by these two blocks.
Even though some part of data can be reused when performing a full search algorithm, and generally there is a speed-up hardware for support in a system, the full search algorithm involves a huge amount of complex computations. For example, if the maximum number of pixels in a possible motion region is m, each block corresponding to the searching region has (2m+1)2 checking points. And there are N2 pixels in each block, so that it is necessary to process N2 computations of SAD for each checking point in the searching region. Therefore, the number of computations in performing a full search algorithm for a block is (2m+1)2×N2. Such a huge amount of computation in a full search algorithm can sometimes occupy 80% of the computation of video processing.
For achieving the object of less computation, many block matching motion estimation algorithms have been developed, such as the three step search, new three step search, one-dimensional full search, four-step search, center-biased diamond search, and the advanced diamond zonal search which is well known. The computations of these algorithms are less than the full search algorithm, but the above algorithms cannot reduce the computation amount by effective data reuse.